{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Latest Time to Catch a Bus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: latestTimeCatchTheBus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #坐上公交的最晚时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>buses</code>&nbsp;，其中&nbsp;<code>buses[i]</code>&nbsp;表示第 <code>i</code>&nbsp;辆公交车的出发时间。同时给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>m</code>&nbsp;的整数数组&nbsp;<code>passengers</code>&nbsp;，其中&nbsp;<code>passengers[j]</code>&nbsp;表示第&nbsp;<code>j</code>&nbsp;位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>capacity</code>&nbsp;，表示每辆公交车&nbsp;<strong>最多</strong>&nbsp;能容纳的乘客数目。</p>\n",
    "\n",
    "<p>每位乘客都会搭乘下一辆有座位的公交车。如果你在 <code>y</code>&nbsp;时刻到达，公交在&nbsp;<code>x</code>&nbsp;时刻出发，满足&nbsp;<code>y &lt;= x</code>&nbsp;&nbsp;且公交没有满，那么你可以搭乘这一辆公交。<strong>最早</strong>&nbsp;到达的乘客优先上车。</p>\n",
    "\n",
    "<p>返回你可以搭乘公交车的最晚到达公交站时间。你 <strong>不能</strong>&nbsp;跟别的乘客同时刻到达。</p>\n",
    "\n",
    "<p><strong>注意：</strong>数组&nbsp;<code>buses</code> 和&nbsp;<code>passengers</code>&nbsp;不一定是有序的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>buses = [10,20], passengers = [2,17,18,19], capacity = 2\n",
    "<b>输出：</b>16\n",
    "<strong>解释：</strong>\n",
    "第 1 辆公交车载着第 1 位乘客。\n",
    "第 2 辆公交车载着你和第 2 位乘客。\n",
    "注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2\n",
    "<b>输出：</b>20\n",
    "<b>解释：</b>\n",
    "第 1 辆公交车载着第 4 位乘客。\n",
    "第 2 辆公交车载着第 6 位和第 2 位乘客。\n",
    "第 3 辆公交车载着第 1 位乘客和你。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == buses.length</code></li>\n",
    "\t<li><code>m == passengers.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m, capacity &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= buses[i], passengers[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>buses</code>&nbsp;中的元素 <strong>互不相同&nbsp;</strong>。</li>\n",
    "\t<li><code>passengers</code>&nbsp;中的元素 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-latest-time-to-catch-a-bus](https://leetcode.cn/problems/the-latest-time-to-catch-a-bus/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-latest-time-to-catch-a-bus](https://leetcode.cn/problems/the-latest-time-to-catch-a-bus/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,20]\\n[2,17,18,19]\\n2', '[20,30,10]\\n[19,13,26,4,25,11,21]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        print(passengers)\n",
    "        m = len(passengers)\n",
    "        idx = 0\n",
    "        for i in buses:\n",
    "            full = False\n",
    "            for j in range(idx, idx + capacity):\n",
    "                if j == m or passengers[j] > i:\n",
    "                    j -= 1\n",
    "                    break\n",
    "            if j - idx == capacity - 1:\n",
    "                full = True\n",
    "            idx = j + 1\n",
    "        idx -= 1\n",
    "        if not full and passengers[idx] != buses[-1]:\n",
    "            return buses[-1]\n",
    "        ans = 1\n",
    "        t = passengers[idx]\n",
    "        while passengers[idx - ans] == t - ans:\n",
    "            ans += 1\n",
    "        # print(idx, passengers[idx])\n",
    "        return t - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        l, m = 0, len(passengers)\n",
    "        ans = 1\n",
    "        print(buses)\n",
    "        print(passengers)\n",
    "        for b in buses:\n",
    "            r = l\n",
    "            while r < m and r - l < capacity and passengers[r] <= b:\n",
    "                if passengers[max(0, r - 1)] + 1 != passengers[r]:\n",
    "                    ans = passengers[r] - 1\n",
    "                r += 1\n",
    "            batch = passengers[l : r]\n",
    "            \n",
    "            t = len(batch)\n",
    "            if not t:\n",
    "                ans = b\n",
    "            elif t < capacity:\n",
    "                if passengers[min(m - 1, r - 1)] != b and passengers[min(m - 1, r)] != b:\n",
    "                    ans = b\n",
    "            print(batch, l, r, b, ans)\n",
    "            l = r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        nb = len(buses)\n",
    "        np = len(passengers)\n",
    "        i = 0\n",
    "        flag = False\n",
    "        flag2 = False\n",
    "        for j, bus in enumerate(buses):\n",
    "            for k in range(capacity):\n",
    "                if passengers[i] <= bus:\n",
    "                    i += 1\n",
    "                    if i == np:\n",
    "                        if j != nb - 1 or k != capacity - 1:\n",
    "                            flag = True\n",
    "                        break\n",
    "                else:\n",
    "                    if j == nb - 1:\n",
    "                        flag2 = True\n",
    "                    break\n",
    "            if i == np:\n",
    "                break\n",
    "        \n",
    "        if flag:\n",
    "            ans = buses[-1]\n",
    "            idx = np - 1\n",
    "        elif i == 0:\n",
    "            return buses[-1]\n",
    "        else:\n",
    "            ans = passengers[i-1] if not flag2 else buses[-1]\n",
    "            idx = i - 1\n",
    "        while idx >= 0 and passengers[idx] == ans:\n",
    "            ans -= 1\n",
    "            idx -= 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort() \n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for i , t in enumerate (buses) :\n",
    "            c= capacity \n",
    "            while c and j < len(passengers) and passengers[j] <= t :\n",
    "                c-=1\n",
    "                j+=1            \n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans :\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort() #对车出发时间进行排序\n",
    "        passengers.sort() #对乘客到达时间进行排序\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j]<=t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        n = len(passengers)\n",
    "        passengers.sort()\n",
    "        buses.sort()\n",
    "        last_i = 0\n",
    "\n",
    "        for b in buses:\n",
    "            rest = capacity\n",
    "            while rest and last_i < n and passengers[last_i] <= b:\n",
    "                rest -= 1\n",
    "                last_i += 1\n",
    "\n",
    "        last_i -= 1\n",
    "        print(passengers)\n",
    "        print(last_i)\n",
    "\n",
    "        if rest:\n",
    "            ret = buses[-1]\n",
    "        else:\n",
    "            ret = passengers[last_i]\n",
    "            \n",
    "        while last_i >= 0 and ret == passengers[last_i]:\n",
    "            last_i -= 1\n",
    "            ret -= 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n, m = len(buses), len(passengers)\n",
    "        count = 0\n",
    "        i = 0\n",
    "        for t in buses:\n",
    "            count = 0\n",
    "            while count < capacity and i < m and passengers[i] <= t:\n",
    "                i += 1\n",
    "                count += 1\n",
    "        res = buses[n-1] if count < capacity else passengers[i-1]\n",
    "        i -= 1\n",
    "        while i >= 0 and res == passengers[i]:\n",
    "            res -= 1\n",
    "            i -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        left = 0\n",
    "        for x in buses:\n",
    "            right = left\n",
    "            while right < len(passengers) and right - left + 1 <= capacity and passengers[right] <= x:\n",
    "                right += 1\n",
    "            full = right - left + 1 > capacity\n",
    "            # print(x, left, right, full)\n",
    "            left = right\n",
    "       \n",
    "        left = max(0, left - 1)\n",
    "        if not full:\n",
    "            print(buses, '111')\n",
    "            if buses[-1] != passengers[left]:\n",
    "                return buses[-1]\n",
    "        # print(left)\n",
    "        for i in range(left, 0, -1):\n",
    "            if passengers[i - 1] + 1 != passengers[i]:\n",
    "                return passengers[i] - 1\n",
    "            \n",
    "        return passengers[0] - 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        n=len(buses)\n",
    "        m=len(passengers)\n",
    "        buses.sort()\n",
    "        print(buses)\n",
    "        passengers.sort()\n",
    "        print(passengers)\n",
    "\n",
    "        p=0\n",
    "        for i in range(n):\n",
    "            c=capacity\n",
    "            while(p<m and c>0):\n",
    "                print(i, p, buses[i], passengers[p])\n",
    "                if passengers[p]<=buses[i]:\n",
    "                    c-=1\n",
    "                    p+=1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        p-=1\n",
    "\n",
    "        q=p\n",
    "        if c>0 and passengers[q]!=buses[i]:\n",
    "            return buses[i] \n",
    "             \n",
    "        \n",
    "        while True:\n",
    "            if q==0:\n",
    "                return passengers[0]-1\n",
    "            elif passengers[q]-passengers[q-1]>1:\n",
    "                print(q)\n",
    "                return passengers[q]-1\n",
    "            else:\n",
    "                q-=1\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        m, n = len(buses), len(passengers)\n",
    "        bIndex, pIndex ,space= 0, 0,0\n",
    "        while bIndex < m and pIndex < n :\n",
    "            space = capacity\n",
    "            while space and pIndex < n and passengers[pIndex] <= buses[bIndex]:\n",
    "                space -= 1\n",
    "                pIndex += 1\n",
    "            print(bIndex, pIndex,space, '!!!')\n",
    "            bIndex += 1\n",
    "        print(pIndex, '@@@')\n",
    "        if bIndex<m:\n",
    "            return buses[-1]\n",
    "        if space > 0:  # 说明此时是最后一辆车（因为有多余车的情况在上面已被考虑）,且还没满\n",
    "            time = buses[-1]\n",
    "            while passengers.count(time):\n",
    "                time -= 1\n",
    "            return time\n",
    "        ans = pIndex - 1 if space == 0 else pIndex \n",
    "        while passengers[ans - 1] + 1 == passengers[ans]:\n",
    "            ans -= 1\n",
    "\n",
    "        return passengers[ans] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        l, m = 0, len(passengers)\n",
    "        ans = 1\n",
    "        print(buses)\n",
    "        print(passengers)\n",
    "        for b in buses:\n",
    "            r = l\n",
    "            while r < m and r - l < capacity and passengers[r] <= b:\n",
    "                if passengers[max(0, r - 1)] + 1 != passengers[r]:\n",
    "                    ans = passengers[r] - 1\n",
    "                r += 1\n",
    "            batch = passengers[l : r]\n",
    "            \n",
    "            t = len(batch)\n",
    "            if not t:\n",
    "                ans = b\n",
    "            elif t < capacity:\n",
    "                if passengers[min(m - 1, r - 1)] != b:\n",
    "                    ans = b\n",
    "            # print(batch, l, r, b, ans)\n",
    "            l = r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for i in range(len(buses)):\n",
    "            temp = capacity\n",
    "            while j<len(passengers):\n",
    "                if temp == 0 or passengers[j]>buses[i]:\n",
    "                    break\n",
    "                temp -=1\n",
    "                j+=1\n",
    "        \n",
    "        if i == len(buses)-1 and temp == 0:\n",
    "            res = passengers[j-1]-1\n",
    "            while res in passengers:\n",
    "                res-=1\n",
    "            return res\n",
    "        else:\n",
    "            res = buses[-1]\n",
    "            while res in passengers:\n",
    "                res-=1\n",
    "            return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses = sorted(buses)\n",
    "        passengers = sorted(passengers)\n",
    "        num_p_gone = 0\n",
    "        num_b_gone = 0\n",
    "        arr_before_p = -1\n",
    "        arr_at_b = -1\n",
    "        while True:\n",
    "            if num_b_gone == len(buses):\n",
    "                break\n",
    "            p_on_cur_b = 0\n",
    "            while (num_p_gone < len(passengers)) and (passengers[num_p_gone] <= buses[num_b_gone]) and (p_on_cur_b < capacity):\n",
    "                if (num_p_gone > arr_before_p) and ( (num_p_gone==0) or (passengers[num_p_gone] > passengers[num_p_gone-1]+1)):\n",
    "                    arr_before_p = num_p_gone\n",
    "                num_p_gone += 1\n",
    "                p_on_cur_b += 1\n",
    "            if (p_on_cur_b == 0) or ( (p_on_cur_b < capacity) and (buses[num_b_gone]>passengers[num_p_gone-1]) ):\n",
    "                arr_at_b = num_b_gone\n",
    "            num_b_gone += 1\n",
    "        if arr_at_b == -1:\n",
    "            return passengers[arr_before_p]-1\n",
    "        elif arr_before_p == -1:\n",
    "            return buses[arr_at_b]\n",
    "        else:\n",
    "            return max(passengers[arr_before_p]-1, buses[arr_at_b])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        pcur = 0\n",
    "        for i in buses:\n",
    "            x = 0\n",
    "            while x < capacity and pcur + x < len(passengers) and passengers[pcur + x] <= i:\n",
    "                x += 1\n",
    "            pcur += x\n",
    "            if x < capacity:\n",
    "                ans = i\n",
    "            else:\n",
    "                ans = passengers[pcur - 1] - 1\n",
    "        while ans in passengers:\n",
    "            ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        # 双指针模拟乘客上车过程\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j] # 在发车时到达公交站or上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans: # 往前找每人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\r\n",
    "        # k = 1\r\n",
    "        # buses.sort(reverse = True)\r\n",
    "        # passengers.sort(reverse = True)\r\n",
    "        # i = len(passengers)-1\r\n",
    "        # j = len(buses)-1\r\n",
    "        # while i >= 0 and j >= 0:\r\n",
    "        #     p = 0\r\n",
    "        #     t = buses[j]\r\n",
    "        #     while i >= 0 and passengers[i] <= t and p < capacity:\r\n",
    "        #         if passengers[i] -1 not in passengers:\r\n",
    "        #             k = passengers[i] -1\r\n",
    "        #         i-=1\r\n",
    "        #         p+=1\r\n",
    "        #     j-=1\r\n",
    "        # if j >= 0:\r\n",
    "        #     return buses[0]\r\n",
    "        # else:\r\n",
    "        #     if i < 0:\r\n",
    "        #         if p < capacity and passengers[0] != buses[0]:\r\n",
    "        #             return buses[0]\r\n",
    "        #     else:\r\n",
    "        #         return k\r\n",
    "        buses.sort()\r\n",
    "        passengers.sort()\r\n",
    "        j = 0\r\n",
    "        for t in buses:\r\n",
    "            c = capacity\r\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\r\n",
    "                c -= 1\r\n",
    "                j += 1\r\n",
    "        j -= 1\r\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\r\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\r\n",
    "            ans -= 1\r\n",
    "            j -= 1\r\n",
    "        return ans\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        res = 1\n",
    "        j = 0\n",
    "        for b in buses:\n",
    "            cnt = 0\n",
    "            while j < len(passengers):\n",
    "                if passengers[j] <= b:\n",
    "                    cnt += 1\n",
    "                    if j == 0:\n",
    "                        res = passengers[j]-1\n",
    "                    else:\n",
    "                        if passengers[j]-1 != passengers[j-1]:\n",
    "                            res = passengers[j]-1\n",
    "                    j += 1\n",
    "                    if cnt == capacity:\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "            if cnt == 0:\n",
    "                res = b\n",
    "            elif cnt < capacity and cnt > 0:\n",
    "                res = (b if b!=passengers[j-1] else res)\n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        # passage = copy.deepcopy(passengers)\n",
    "        j = 0\n",
    "        for i in range(len(buses)):\n",
    "            c = capacity\n",
    "            while c > 0 and j < len(passengers) and passengers[j] <= buses[i]:\n",
    "                c -= 1\n",
    "                j += 1 #因为前面+1了\n",
    "        j -= 1#减1\n",
    "        ans = buses[-1] if c > 0 else passengers[j]\n",
    "        while j >= 0 and ans == passengers[j]:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            #每个时间段，搭载的乘客\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        #最后一班车还有空位，只要在最后一班车发车时间上车即可\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        #最后一班车没有空位，找到前一个上车的乘客，顺着他往前，找到一个没人到达的时刻\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j=0\n",
    "        for bus in buses:\n",
    "            c=capacity\n",
    "            while c>0 and j<len(passengers) and passengers[j]<=bus:\n",
    "                c-=1\n",
    "                j+=1\n",
    "        j-=1\n",
    "        ans=buses[-1] if c>0 else passengers[j]\n",
    "        while ans==passengers[j] and j>=0:\n",
    "            ans-=1\n",
    "            j-=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        # 核心思想:贪心\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        # 1.找最后一个乘客是谁\n",
    "        j = 0\n",
    "        for i,v in enumerate(buses):\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= v:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        # 2.从最后一个乘客开始往前找空位\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        m, n = len(buses), len(passengers)\n",
    "        bIndex, pIndex ,space= 0, 0,0\n",
    "        while bIndex < m and pIndex < n :\n",
    "            space = capacity\n",
    "            while space and pIndex < n and passengers[pIndex] <= buses[bIndex]:\n",
    "                space -= 1\n",
    "                pIndex += 1\n",
    "            # print(bIndex, pIndex,space, '!!!')\n",
    "            bIndex += 1\n",
    "        # print(pIndex, '@@@')\n",
    "        if bIndex<m:\n",
    "            return buses[-1]\n",
    "        if space > 0:  # 说明此时是最后一辆车（因为有多余车的情况在上面已被考虑）,且还没满\n",
    "            time = buses[-1]\n",
    "            while passengers.count(time):\n",
    "                time -= 1\n",
    "            return time\n",
    "        ans = pIndex - 1  \n",
    "        while passengers[ans - 1] + 1 == passengers[ans]:\n",
    "            ans -= 1\n",
    "\n",
    "        return passengers[ans] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        l, m, ans = 0, len(passengers), 1\n",
    "        for b in buses:\n",
    "            r = l\n",
    "            while r < m and r - l < capacity and passengers[r] <= b:\n",
    "                if passengers[max(0, r - 1)] + 1 != passengers[r]:\n",
    "                    ans = passengers[r] - 1\n",
    "                r += 1\n",
    "            batch = passengers[l : r]\n",
    "            t = len(batch)\n",
    "            if not t:\n",
    "                ans = b\n",
    "            elif t < capacity:\n",
    "                if passengers[min(m - 1, r - 1)] != b:\n",
    "                    ans = b\n",
    "            l = r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j=0\n",
    "        time=0\n",
    "        for t in buses:\n",
    "            c=capacity\n",
    "            while c and j < len(passengers) and passengers[j]<=t :\n",
    "                c-=1\n",
    "                j+=1\n",
    "        j-=1\n",
    "        if c==0:\n",
    "            time=passengers[j]\n",
    "        else:\n",
    "            time=t\n",
    "        while j>=0 and time==passengers[j]:\n",
    "            j-=1\n",
    "            time-=1\n",
    "        return time\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        m, n = len(buses), len(passengers)\n",
    "        bIndex, pIndex ,space= 0, 0,0\n",
    "        while bIndex < m and pIndex < n :\n",
    "            space = capacity\n",
    "            while space and pIndex < n and passengers[pIndex] <= buses[bIndex]:\n",
    "                space -= 1\n",
    "                pIndex += 1\n",
    "            # print(bIndex, pIndex,space, '!!!')\n",
    "            bIndex += 1\n",
    "        # print(pIndex, '@@@')\n",
    "        if bIndex<m:\n",
    "            return buses[-1]\n",
    "        if space > 0:  # 说明此时是最后一辆车（因为有多余车的情况在上面已被考虑）,且还没满\n",
    "            time = buses[-1]\n",
    "            while passengers.count(time):\n",
    "                time -= 1\n",
    "            return time\n",
    "        ans = pIndex - 1 if space == 0 else pIndex \n",
    "        while passengers[ans - 1] + 1 == passengers[ans]:\n",
    "            ans -= 1\n",
    "\n",
    "        return passengers[ans] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j=0\n",
    "        time=0\n",
    "        for t in buses:\n",
    "            c=capacity\n",
    "            while c and j < len(passengers) and passengers[j]<=t :\n",
    "                c-=1\n",
    "                j+=1\n",
    "        j-=1\n",
    "        if c==0:\n",
    "            time=passengers[j]\n",
    "        else:\n",
    "            time=t\n",
    "        while j>=0 and time==passengers[j]:\n",
    "            j-=1\n",
    "            time-=1\n",
    "        return time\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j=0\n",
    "        for i,b in enumerate(buses):\n",
    "            c=capacity\n",
    "            while j<len(passengers) and c>0 and passengers[j]<=b:\n",
    "                c -=1\n",
    "                j +=1\n",
    "        j -=1\n",
    "        res=buses[-1]if c else passengers[j]\n",
    "        while j>=0 and res==passengers[j]:\n",
    "            j -=1\n",
    "            res -=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        nb = len(buses)\n",
    "        np = len(passengers)\n",
    "        i = 0\n",
    "        flag = False\n",
    "        for j, bus in enumerate(buses):\n",
    "            for k in range(capacity):\n",
    "                if passengers[i] <= bus:\n",
    "                    i += 1\n",
    "                    if i == np:\n",
    "                        if k != capacity - 1:\n",
    "                            flag = True\n",
    "                        break\n",
    "                else:\n",
    "                    if j == nb - 1:\n",
    "                        flag = True\n",
    "                    break\n",
    "            if i == np:\n",
    "                if j != nb - 1:\n",
    "                    flag = True\n",
    "                break\n",
    "        \n",
    "        i -= 1\n",
    "        ans = passengers[i] if not flag else buses[-1]\n",
    "        while i >= 0 and passengers[i] == ans:\n",
    "            ans -= 1\n",
    "            i -= 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        p = 0\n",
    "\n",
    "        for bus in buses:\n",
    "            c = capacity\n",
    "            while c and p < len(passengers) and passengers[p]<=bus:\n",
    "                p += 1\n",
    "                c -= 1\n",
    "\n",
    "        p -= 1 #最后一位上车的乘客\n",
    "        ans =  buses[-1] if c else passengers[p] #车上还有座位，则为最后发车时间，否则为最后一位乘客上车时间\n",
    "        while ans in passengers: #如果ans在乘客表中，则-1\n",
    "            ans -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        j = 0\n",
    "        buses.sort()\n",
    "        n = len(passengers)\n",
    "        passengers.sort()\n",
    "        for bus in buses:\n",
    "            c = capacity\n",
    "            while c and j < n and passengers[j] <= bus:\n",
    "                j += 1\n",
    "                c -= 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and ans == passengers[j]:\n",
    "            j -= 1\n",
    "            ans -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j=0\n",
    "        for bus in buses:\n",
    "            c=capacity\n",
    "            while c>0 and j<len(passengers) and passengers[j]<=bus:\n",
    "                c-=1\n",
    "                j+=1\n",
    "        j-=1\n",
    "        ans=buses[-1] if c>0 else passengers[j]\n",
    "        while ans==passengers[j] and j>=0:\n",
    "            ans-=1\n",
    "            j-=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        \n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        \n",
    "        i = 0\n",
    "        m = len(passengers)\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and i <= m-1 and passengers[i] <= t:\n",
    "                c -= 1\n",
    "                i += 1\n",
    "        # 最后一个乘客的时间\n",
    "        i -= 1\n",
    "        # 初始化\n",
    "        ans = buses[-1] if c else passengers[i]\n",
    "        # 往前找第一个每人的时间\n",
    "        while i >= 0 and ans == passengers[i]:\n",
    "            ans -= 1\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        passenger_pos = 0\n",
    "        # 每一个bus，在达到capacity之前，把时间符合的都装进来，达没装满就更新最晚的时间，也就是bus的时间\n",
    "        # 然后换下一辆bus\n",
    "        for i, bus_time in enumerate(buses):\n",
    "            c = capacity\n",
    "            while c and passenger_pos < len(passengers) and passengers[passenger_pos] <= bus_time:\n",
    "                # 这辆车还能装人 and 还有乘客 and 这个乘客不晚于这辆车\n",
    "                c -= 1\n",
    "                passenger_pos += 1\n",
    "        \n",
    "        # 到最后剩下的这个人就是最后一个没上车的人\n",
    "        # 那我们可以插队到他前面去（顶替他前面的那个上了车的人）\n",
    "        passenger_pos -= 1\n",
    "        ans = buses[-1] if c else passengers[passenger_pos]\n",
    "        # 如果c > 0，也就是代表这辆车无论是否是最后一辆，最后一辆车都有空位，那ans取最后一辆车\n",
    "        # 如果c == 0，那么这辆车一定是最后一辆车，而且所有车的所有位置都满了，那我就顶替最后一个上车的人\n",
    "\n",
    "        # 找到了之后，但是题目要求是乘客到达时间不能一样，那我就比这个最后一个上车的早一分钟\n",
    "        # 如果是bus[-1]，\n",
    "        while passenger_pos >= 0 and passengers[passenger_pos] == ans:\n",
    "            passenger_pos -= 1\n",
    "            ans -= 1\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j=0\n",
    "        for t in buses:\n",
    "            c=capacity\n",
    "            while c and j<len(passengers) and passengers[j]<=t:\n",
    "                c-=1\n",
    "                j+=1\n",
    "        j-=1\n",
    "        ans=buses[-1] if c else passengers[j]\n",
    "        while j>=0 and passengers[j]==ans:\n",
    "            ans-=1\n",
    "            j-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        i,j = 0,0\n",
    "        while i <len(buses) and j<len(passengers):\n",
    "            now_cap = 0\n",
    "            while now_cap < capacity and j< len(passengers) and passengers[j]<=buses[i]:\n",
    "                now_cap+=1\n",
    "                j+=1\n",
    "            i+=1\n",
    "        # 回退到最后一个上车的人\n",
    "        j-=1\n",
    "        if now_cap < capacity or i<len(buses):  # 如果有空位或者还有剩余车辆\n",
    "            res = buses[len(buses)-1]   # 直接从最末班车开始计算\n",
    "        else:\n",
    "            res = passengers[j]         # 定位到最后一个上车的人\n",
    "        while res in passengers:        \n",
    "            res -=1                     # 从这往前找第一个空位\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort(), passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort(), passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while j < len(passengers) and passengers[j] <= t and c > 0:\n",
    "                j += 1\n",
    "                c -= 1\n",
    "        # if c:\n",
    "        #     return buses[-1]\n",
    "        j = j - 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        # ans = passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n",
    "\n",
    "        # class Solution:\n",
    "    # def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "    #     buses.sort()\n",
    "    #     passengers.sort()\n",
    "    #     j = 0\n",
    "    #     for t in buses:\n",
    "    #         c = capacity\n",
    "    #         while c and j < len(passengers) and passengers[j] <= t:\n",
    "    #             c -= 1\n",
    "    #             j += 1\n",
    "    #     j -= 1\n",
    "    #     ans = buses[-1] if c else passengers[j]\n",
    "    #     while j >= 0 and passengers[j] == ans:\n",
    "    #         ans -= 1\n",
    "    #         j -= 1\n",
    "    #     return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j >= 0 and passengers[j] == ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        p = 0\n",
    "\n",
    "        for bus in buses:\n",
    "            c = capacity\n",
    "            while c and p < len(passengers) and passengers[p]<=bus:\n",
    "                p += 1\n",
    "                c -= 1\n",
    "\n",
    "        p -= 1 #最后一位上车的乘客\n",
    "        ans =  buses[-1] if c else passengers[p]\n",
    "        while ans in passengers:\n",
    "            ans -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j < len(passengers) and passengers[j] <= t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]  # 在发车时到达公交站 or 上一个上车的乘客\n",
    "        while j >= 0 and passengers[j] == ans:  # 往前找没人到达的时刻\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\r\n",
    "        buses.sort()\r\n",
    "        passengers.sort()\r\n",
    "        cur = 0 \r\n",
    "        c = 0 \r\n",
    "        for t in buses:\r\n",
    "            c = capacity\r\n",
    "            while c and cur < len(passengers) and passengers[cur] <= t:\r\n",
    "                c -= 1 \r\n",
    "                cur += 1 \r\n",
    "        cur -= 1 \r\n",
    "        res = buses[-1] if c else passengers[cur]\r\n",
    "        while cur >= 0 and passengers[cur] == res:\r\n",
    "            cur -= 1\r\n",
    "            res -= 1\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        inf = avail = lastP = float('inf')\n",
    "        itB = iter(buses)\n",
    "        bus = next(itB)\n",
    "        remain = capacity\n",
    "        for lastP, p in zip(chain([0], passengers), chain(passengers, [inf])):\n",
    "            while p > bus:\n",
    "                if remain and lastP < bus:\n",
    "                    avail = bus\n",
    "                bus = next(itB, 0)\n",
    "                if not bus: break\n",
    "                remain = capacity\n",
    "            if not bus: break\n",
    "            remain -= 1\n",
    "            if p - 1 > lastP:\n",
    "                avail = p - 1\n",
    "            if not remain: \n",
    "                remain = capacity\n",
    "                bus = next(itB, 0)\n",
    "                if not bus: break\n",
    "        return avail\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        # 排序后，用双指针模拟乘客上车的过程：遍历公交车，找哪些乘客可以上车\n",
    "        # 模拟结束后\n",
    "        # 1.如果最后一班公交还有空位，我们可以在发车时到达公交站。\n",
    "        # 如果此刻有人，我们可以顺着他往前找到没人到达的时刻\n",
    "        # 2.如果最后一班公交没有空位，我们可以找到上一个上车的乘客，\n",
    "        # 顺着他往前找到一个没人到达的时刻\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        pnum = len(passengers)\n",
    "\n",
    "        j = 0\n",
    "        for t in buses:\n",
    "            c = capacity\n",
    "            while c and j<pnum and passengers[j]<=t:\n",
    "                c -= 1\n",
    "                j += 1\n",
    "        j -= 1\n",
    "        ans = buses[-1] if c else passengers[j]\n",
    "        while j>=0 and passengers[j]==ans:\n",
    "            ans -= 1\n",
    "            j -= 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        occ = {}\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        busid = 0\n",
    "        busca = 0\n",
    "        lastcan = 0\n",
    "        for i in passengers:\n",
    "            while(busca == capacity or (busid < len(buses) and i > buses[busid])):\n",
    "                if busca < capacity:\n",
    "                    lastcan = buses[busid]\n",
    "                busca = 0\n",
    "                busid += 1\n",
    "            if busid >= len(buses):\n",
    "                break\n",
    "            if i <= buses[busid] and busca < capacity:\n",
    "                busca += 1\n",
    "                lastcan = i\n",
    "                occ[i] = 1\n",
    "        if busca < capacity and busid == len(buses) - 1:\n",
    "            lastcan = buses[-1]\n",
    "        if busid < len(buses) - 1:\n",
    "            lastcan = buses[-1]\n",
    "        while occ.get(lastcan, 0) == 1:\n",
    "            lastcan -= 1\n",
    "        return lastcan\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n = len(buses)\n",
    "        m = len(passengers)\n",
    "        \n",
    "        # print(buses, passengers)\n",
    "        num = [0] * n\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        while i < n:\n",
    "            while j < m and buses[i] >= passengers[j] and num[i] < capacity:\n",
    "                j += 1\n",
    "                num[i] += 1\n",
    "            i += 1\n",
    "        # print(num, j)\n",
    "        ans = 0\n",
    "        j -= 1\n",
    "        s = set(passengers)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            tmp = buses[i] if num[i] < capacity else passengers[j]\n",
    "            # print(tmp)\n",
    "            # if num[i] < capacity:\n",
    "            # tmp = buses[i]\n",
    "            while tmp in passengers:\n",
    "                tmp -= 1\n",
    "            return tmp\n",
    "            # else:\n",
    "            #     j -= capacity\n",
    "        \n",
    "                \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n_passenger = len(passengers)\n",
    "        p = 0\n",
    "        for y in buses:\n",
    "            c = capacity\n",
    "            while c and p < n_passenger and passengers[p] <= y:\n",
    "                c -= 1\n",
    "                p += 1\n",
    "        latest = p - 1   # 找到了最后一个上车的乘客\n",
    "        # 如果还有空位，就在最后一刻上车，否则就从最后一位乘客开始往前插队\n",
    "        ans = buses[-1] if c else passengers[latest]\n",
    "        passengers = set(passengers)\n",
    "        while ans in passengers:\n",
    "            ans -= 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        used = set(passengers)\n",
    "        l=0\n",
    "        r=max(buses[-1], passengers[-1])\n",
    "        def cando(x):\n",
    "            p = [c for c in passengers if c<=x]+[x]\n",
    "            p.sort()\n",
    "            # print(p)\n",
    "            q=deque(p)\n",
    "            n=len(buses)\n",
    "            rest = [capacity]*n\n",
    "            for i, bus in enumerate(buses):\n",
    "                while rest[i] and q and q[0]<=bus:\n",
    "                    rest[i]-=1\n",
    "                    q.popleft()\n",
    "            # print(not bool(q))\n",
    "            return not bool(q)\n",
    "        while l<=r:\n",
    "            x=(l+r)//2\n",
    "            if not cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        # l-1往前找不在集合中的\n",
    "        l-=1\n",
    "        while l and l in used:\n",
    "            l-=1\n",
    "        return l\n",
    "\n",
    "    def latestTimeCatchTheBus1(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n=len(buses)\n",
    "        ans = passengers[0]-1\n",
    "        q = deque(passengers)\n",
    "        tot = set(passengers)\n",
    "        used = [[] for _ in range(n)]\n",
    "        \n",
    "        rest = [capacity]*n\n",
    "        \n",
    "\n",
    "        for i,bus in enumerate(buses):\n",
    "            while q and rest[i] and q[0]<=bus:\n",
    "                rest[i] -=1\n",
    "                c = q.popleft()\n",
    "                used[i].append(c)\n",
    "                if c-1 not in tot:\n",
    "                    ans = c-1\n",
    "            if rest[i]==capacity:\n",
    "                ans = bus\n",
    "        print(used)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses = sorted(buses)\n",
    "        passengers = sorted(passengers)\n",
    "        print(passengers)\n",
    "        passenger_dict = {}\n",
    "        by_index = -1\n",
    "        byBus = 0\n",
    "        for i in range(len(buses)):\n",
    "            bus = buses[i]\n",
    "            byBus = capacity\n",
    "            while byBus > 0 and by_index + 1 < len(passengers):\n",
    "                by_index += 1\n",
    "                byBus -= 1\n",
    "                if passengers[by_index] > bus:\n",
    "                    by_index -= 1\n",
    "                    byBus += 1\n",
    "                    break\n",
    "                passenger_dict[passengers[by_index]] = True\n",
    "        res = 0\n",
    "        last_time = passengers[by_index]\n",
    "        if byBus > 0:\n",
    "            last_time = buses[-1]\n",
    "        for i in range(last_time, -1, -1):\n",
    "            if i not in passenger_dict:\n",
    "                res = i\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        used = set(passengers)\n",
    "        l=0\n",
    "        r=max(buses[-1], passengers[-1])\n",
    "        def cando(x):\n",
    "            p = [c for c in passengers if c<=x]+[x]\n",
    "            # p.sort()\n",
    "            # print(p)\n",
    "            q=deque(p)\n",
    "            n=len(buses)\n",
    "            rest = [capacity]*n\n",
    "            for i, bus in enumerate(buses):\n",
    "                while rest[i] and q and q[0]<=bus:\n",
    "                    rest[i]-=1\n",
    "                    q.popleft()\n",
    "            # print(not bool(q))\n",
    "            return not bool(q)\n",
    "        while l<=r:\n",
    "            x=(l+r)//2\n",
    "            if not cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        # l-1往前找不在集合中的\n",
    "        l-=1\n",
    "        while l and l in used:\n",
    "            l-=1\n",
    "        return l\n",
    "\n",
    "    def latestTimeCatchTheBus1(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n=len(buses)\n",
    "        ans = passengers[0]-1\n",
    "        q = deque(passengers)\n",
    "        tot = set(passengers)\n",
    "        used = [[] for _ in range(n)]\n",
    "        \n",
    "        rest = [capacity]*n\n",
    "        \n",
    "\n",
    "        for i,bus in enumerate(buses):\n",
    "            while q and rest[i] and q[0]<=bus:\n",
    "                rest[i] -=1\n",
    "                c = q.popleft()\n",
    "                used[i].append(c)\n",
    "                if c-1 not in tot:\n",
    "                    ans = c-1\n",
    "            if rest[i]==capacity:\n",
    "                ans = bus\n",
    "        print(used)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        used = set(passengers)\n",
    "        l=0\n",
    "        r=max(buses[-1], passengers[-1])\n",
    "        def cando(x):\n",
    "            p = [c for c in passengers if c<=x]+[x]\n",
    "            # p.sort()\n",
    "            # print(p)\n",
    "            q=deque(p)\n",
    "            n=len(buses)\n",
    "            rest = [capacity]*n\n",
    "            for i, bus in enumerate(buses):\n",
    "                while rest[i] and q and q[0]<=bus:\n",
    "                    rest[i]-=1\n",
    "                    q.popleft()\n",
    "            # print(not bool(q))\n",
    "            return not bool(q)\n",
    "        while l<=r:\n",
    "            x=(l+r)//2\n",
    "            if not cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        # l-1往前找不在集合中的\n",
    "        l-=1\n",
    "        while l and l in used:\n",
    "            l-=1\n",
    "        return l\n",
    "\n",
    "    def latestTimeCatchTheBus1(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n=len(buses)\n",
    "        ans = passengers[0]-1\n",
    "        q = deque(passengers)\n",
    "        tot = set(passengers)\n",
    "        used = [[] for _ in range(n)]\n",
    "        \n",
    "        rest = [capacity]*n\n",
    "        \n",
    "\n",
    "        for i,bus in enumerate(buses):\n",
    "            while q and rest[i] and q[0]<=bus:\n",
    "                rest[i] -=1\n",
    "                c = q.popleft()\n",
    "                used[i].append(c)\n",
    "                if c-1 not in tot:\n",
    "                    ans = c-1\n",
    "            if rest[i]==capacity:\n",
    "                ans = bus\n",
    "        print(used)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        used = set(passengers)\n",
    "        l=0\n",
    "        r=max(buses[-1], passengers[-1])\n",
    "        def cando(x):\n",
    "            p = [c for c in passengers if c<=x]+[x]\n",
    "            # p.sort()\n",
    "            # print(p)\n",
    "            q=deque(p)\n",
    "            n=len(buses)\n",
    "            rest = [capacity]*n\n",
    "            for i, bus in enumerate(buses):\n",
    "                while rest[i] and q and q[0]<=bus:\n",
    "                    rest[i]-=1\n",
    "                    q.popleft()\n",
    "            # print(not bool(q))\n",
    "            return not bool(q)\n",
    "        while l<=r:\n",
    "            x=(l+r)//2\n",
    "            if not cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        # l-1往前找不在集合中的\n",
    "        l-=1\n",
    "        while l and l in used:\n",
    "            l-=1\n",
    "        return l\n",
    "\n",
    "    def latestTimeCatchTheBus1(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n=len(buses)\n",
    "        ans = passengers[0]-1\n",
    "        q = deque(passengers)\n",
    "        tot = set(passengers)\n",
    "        used = [[] for _ in range(n)]\n",
    "        \n",
    "        rest = [capacity]*n\n",
    "        \n",
    "\n",
    "        for i,bus in enumerate(buses):\n",
    "            while q and rest[i] and q[0]<=bus:\n",
    "                rest[i] -=1\n",
    "                c = q.popleft()\n",
    "                used[i].append(c)\n",
    "                if c-1 not in tot:\n",
    "                    ans = c-1\n",
    "            if rest[i]==capacity:\n",
    "                ans = bus\n",
    "        print(used)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        used = set(passengers)\n",
    "        l=0\n",
    "        r=max(buses[-1]+1, passengers[-1])\n",
    "        def cando(x):\n",
    "            p = [c for c in passengers if c<=x]+[x]\n",
    "            # p.sort()\n",
    "            # print(p)\n",
    "            q=deque(p)\n",
    "            n=len(buses)\n",
    "            rest = [capacity]*n\n",
    "            for i, bus in enumerate(buses):\n",
    "                while rest[i] and q and q[0]<=bus:\n",
    "                    rest[i]-=1\n",
    "                    q.popleft()\n",
    "            # print(not bool(q))\n",
    "            return not bool(q)\n",
    "        while l<=r:\n",
    "            x=(l+r)//2\n",
    "            if not cando(x):\n",
    "                r=x-1\n",
    "            else:\n",
    "                l=x+1\n",
    "        # l-1往前找不在集合中的\n",
    "        l-=1\n",
    "        while l and l in used:\n",
    "            l-=1\n",
    "        return l\n",
    "\n",
    "    def latestTimeCatchTheBus1(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n=len(buses)\n",
    "        ans = passengers[0]-1\n",
    "        q = deque(passengers)\n",
    "        tot = set(passengers)\n",
    "        used = [[] for _ in range(n)]\n",
    "        \n",
    "        rest = [capacity]*n\n",
    "        \n",
    "\n",
    "        for i,bus in enumerate(buses):\n",
    "            while q and rest[i] and q[0]<=bus:\n",
    "                rest[i] -=1\n",
    "                c = q.popleft()\n",
    "                used[i].append(c)\n",
    "                if c-1 not in tot:\n",
    "                    ans = c-1\n",
    "            if rest[i]==capacity:\n",
    "                ans = bus\n",
    "        print(used)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers = sorted(passengers)[::-1]\n",
    "        n = len(buses)\n",
    "        ans = []\n",
    "        tem = []\n",
    "        for i in range(n):\n",
    "            temp = buses[i]\n",
    "            res = []\n",
    "            for j in range(capacity):\n",
    "                if passengers and passengers[-1] <= temp:\n",
    "                    res.append(passengers.pop())\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(res)\n",
    "            tem.extend(res)\n",
    "        if len(ans[-1]) < capacity:\n",
    "            for i in range(buses[-1],0,-1):\n",
    "                if i not in ans[-1] and i not in tem:\n",
    "                    return i\n",
    "        else:\n",
    "            for i in range(tem[-1],0,-1):\n",
    "                if i not in tem:\n",
    "                    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], ps: List[int], capacity: int) -> int:\n",
    "        P=set(ps)\n",
    "        q=deque(sorted(ps))\n",
    "        ans=0\n",
    "        for t in sorted(buses):\n",
    "            tmp=capacity\n",
    "            while tmp and q and q[0]<=t:\n",
    "                ans=q.popleft()\n",
    "                tmp-=1\n",
    "            if tmp:ans=t\n",
    "        while ans in P:\n",
    "            ans-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        sl=SortedList()\n",
    "        for i in passengers:\n",
    "            sl.add(i)\n",
    "\n",
    "        go=0\n",
    "\n",
    "        n=len(passengers)\n",
    "\n",
    "        for i in range(len(buses)-1):\n",
    "            thisgo=0\n",
    "            while  sl and sl[0]<=buses[i] and thisgo<capacity:\n",
    "                thisgo+=1\n",
    "                sl.pop(0)\n",
    "\n",
    "        if len(sl)<capacity:\n",
    "            ans=buses[-1]\n",
    "        else:\n",
    "            ans=min(sl[capacity-1]-1,buses[-1])\n",
    "        sett=set(passengers)\n",
    "        while ans in sett:\n",
    "            ans-=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n = len(buses)\n",
    "        cap = [[] for _ in range(n)]\n",
    "        j = 0\n",
    "        passengersSet = set()\n",
    "        for p in passengers:\n",
    "            passengersSet.add(p)\n",
    "            while(j < n and p > buses[j]):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "            cap[j].append(p)\n",
    "            if(len(cap[j]) == capacity):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(len(cap[i]) == 0 or (len(cap[i]) < capacity and cap[i][-1] < buses[i])):\n",
    "                return buses[i]\n",
    "            for j in range(len(cap[i])-1,-1,-1):\n",
    "                if(cap[i][j]-1 not in passengersSet):\n",
    "                    return cap[i][j]-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n = len(buses)\n",
    "        cap = [[] for _ in range(n)]\n",
    "        j = 0\n",
    "        for p in passengers:\n",
    "            while(j < n and p > buses[j]):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "            cap[j].append(p)\n",
    "            if(len(cap[j]) == capacity):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "        passengersSet = set(passengers)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(len(cap[i]) == 0 or (len(cap[i]) < capacity and cap[i][-1] < buses[i])):\n",
    "                return buses[i]\n",
    "            for j in range(len(cap[i])-1,-1,-1):\n",
    "                if(cap[i][j]-1 not in passengersSet):\n",
    "                    return cap[i][j]-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n = len(buses)\n",
    "        cap = [[] for _ in range(n)]\n",
    "        j = 0\n",
    "        for p in passengers:\n",
    "            while(j < n and p > buses[j]):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "            cap[j].append(p)\n",
    "            if(len(cap[j]) == capacity):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "        passengersSet = set(passengers)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(len(cap[i]) == 0 or (len(cap[i]) < capacity and cap[i][-1] < buses[i])):\n",
    "                return buses[i]\n",
    "            for j in range(len(cap[i])-1,-1,-1):\n",
    "                if(cap[i][j]-1 not in passengersSet):\n",
    "                    return cap[i][j]-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "\n",
    "        len_b, len_p = len(buses), len(passengers)\n",
    "        ib, ip = 0, 0\n",
    "        loads = [[] for _ in range(len_b)]\n",
    "\n",
    "        while ib < len_b and ip < len_p:\n",
    "            b, p = buses[ib], passengers[ip]\n",
    "            if p <= b:\n",
    "                if len(loads[ib]) < capacity:\n",
    "                    loads[ib].append(p)\n",
    "                    ip += 1\n",
    "                else:\n",
    "                    ib += 1\n",
    "            else:\n",
    "                ib += 1\n",
    "\n",
    "        # print(loads)\n",
    "        passengers_set = set(passengers)\n",
    "\n",
    "        for ib_reverse, load in enumerate(loads[::-1]):\n",
    "            ib = len_b - ib_reverse - 1\n",
    "            if len(load) < capacity:\n",
    "                for i in range(buses[ib], -1, -1):\n",
    "                    if i not in passengers_set:\n",
    "                        return i\n",
    "            else:\n",
    "                for i in range(len(load) - 1, 0, -1):\n",
    "                    if load[i] - load[i - 1] > 1 and load[i] - 1 not in passengers_set:\n",
    "                        return load[i] - 1\n",
    "                if load[0] - 1 not in passengers_set:\n",
    "                    return load[0] - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:\n",
    "        buses.sort()\n",
    "        passengers.sort()\n",
    "        n = len(buses)\n",
    "        cap = [[] for _ in range(n)]\n",
    "        j = 0\n",
    "        for p in passengers:\n",
    "            while(j < n and p > buses[j]):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "            cap[j].append(p)\n",
    "            if(len(cap[j]) == capacity):\n",
    "                j += 1\n",
    "            if(j == n):\n",
    "                break\n",
    "        passengersSet = set(passengers)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(len(cap[i]) == 0 or (len(cap[i]) < capacity and cap[i][-1] < buses[i])):\n",
    "                return buses[i]\n",
    "            for j in range(len(cap[i])-1,-1,-1):\n",
    "                if(cap[i][j]-1 not in passengersSet):\n",
    "                    return cap[i][j]-1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
